package com.mj.heap;


import java.util.Comparator;

/**
 * 二叉堆(最大堆 )
 * 二叉堆的底层（物理结构）一般用数组实现即可
 *
 * @param <E>
 */
public class BinaryHeap<E> extends AbstractHeap<E>  {
    private E[] elements;
    public static final int DEFAULT_CAPACITY = 10;

    public BinaryHeap(E[] elements, Comparator comparator) {
        super(comparator);
        //需要深拷贝，避免影响数组
        if (elements == null || elements.length == 0) {
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
            this.elements = (E[]) new Object[capacity];
            for (int i = 0; i < elements.length; i++) {
                this.elements[i] = elements[i];
            }
            size = elements.length;
        }
        heapify();

    }


    public BinaryHeap(E[] elements) {
        this(elements, null);
    }


    public BinaryHeap(Comparator<E> comparator) {
        super(comparator);
        this.elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    public BinaryHeap() {
        this(null, null);
    }

    @Override
    public void clear() {
        for (int i = 0; i < elements.length; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    @Override
    public void add(E element) {
        elementNotNullCheck(element);
        ensureCapacity(size + 1);

        elements[size++] = element;

        siftUp(size - 1);
    }

    /**
     * 批量建堆
     */
    private void heapify() {
        //自上而下的上滤 效率慢
//        for (int i = 1; i < size; i++) {
//            siftUp(i);
//        }
        //自下而上的下滤
        for (int i = (size >> 1) - 1; i >=0 ; i--) {
            siftDown(i);
        }
    }

    /**
     * 让index位置的元素上滤
     *
     * @param index 数组位置
     */
//    private void siftUp(int index) {
//        E node = elements[index];
//        //index > 0 才有父节点
//        while (index > 0) {
//            //计算父节点的索引
//            int parentIndex = (index - 1) >> 1;
//            E parent = elements[parentIndex];
//            if (compare(node, parent) <= 0) return;
//
//            //交换index、parentIndex位置的内容
//            E temp = elements[index];
//            elements[index] = elements[parentIndex];
//            elements[parentIndex] = temp;
//
//            //重新赋值index
//            index = parentIndex;
//
//        }
//    }

    /**
     * 让index位置的元素上滤
     * 优化
     *
     * @param index 数组位置
     */
    private void siftUp(int index) {
        E node = elements[index];
        //index > 0 才有父节点
        while (index > 0) {
            //计算父节点的索引
            int parentIndex = (index - 1) >> 1;
            E parent = elements[parentIndex];
            if (compare(node, parent) <= 0) break;

            //交换index位置的内容
            elements[index] = parent;

            //重新赋值index
            index = parentIndex;

        }
        elements[index] = node;
    }

    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (capacity <= oldCapacity) return;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newArray = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newArray[i] = elements[i];
        }
        elements = newArray;
    }

    /**
     * 获取堆顶元素
     *
     * @return
     */
    @Override
    public E get() {
        emptyCheck();
        return elements[0];
    }

    @Override
    public E remove() {
        emptyCheck();
        int lastIndex = --size;
        E root = elements[0];
        E lastNode = elements[lastIndex];
        elements[0] = lastNode;
        elements[lastIndex] = null;


        siftDown(0);
        return root;
    }

    /**
     * 下滤
     * 让index位置的元素下滤
     *
     * @param index
     */
    private void siftDown(int index) {
        E node = elements[index];
        //第一个叶子节点的索引==非叶子节点的数量
        int half = size >> 1;
        // 必须保证index位置是非叶子节点
        while (index < half) {
            // index的节点有两种情况
            // 1.只有左子节点
            // 2.同时有左右子节点

            // 默认为左子节点跟它进行比较
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];

            // 右子节点
            int rightIndex = childIndex + 1;

            //选出左右子节点最大的那个
            if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
//                childIndex = rightIndex;
                child = elements[childIndex = rightIndex];
            }


            if (compare(node, child) >= 0) break;
            // 将子节点存放到index位置
            elements[index] = child;
            // 重新设置index
            index = childIndex;

        }
        elements[index] = node;

    }

    /**
     * 替换堆顶元素
     *
     * @param element
     * @return
     */
    @Override
    public E replace(E element) {
        elementNotNullCheck(element);

        E root = null;
        if (size == 0) {
            elements[size++] = element;
        } else {
            root = elements[0];
            elements[0] = element;
            siftDown(0);
        }
        return root;
    }

    /**
     * 判断是否为空
     */
    private void emptyCheck() {
        if (size == 0) {
            throw new IndexOutOfBoundsException("Heap is empty");
        }
    }

    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null!");
        }
    }

}
